

// function Merge(a, lo, mid, hi) {
// 	let i = lo, j = mid + 1

// 	for(let k = lo; k <= hi; k++) {
// 		aux[k] = a[k]
// 	}

// 	for(let k = lo; k <= hi; k++) {
// 		if (i > mid) {
// 			a[k] = aux[j++]
// 		} else if (j > hi) {
// 			a[k] = aux[i++]
// 		} else if (less(aux[j], aux[i])) {
// 			a[k] = aux[j++]
// 		} else {
// 			a[k] = aux[i++]
// 		}
		
// 	}
// }

const mergeSort = arr => {
	// 采用自上而下的递归方法
	const len = arr.length
	if (len < 2) {
		return arr
	}
	let middle = Math.floor(len / 2),
		left = arr.slice(0, middle),
		right = arr.slice(middle)

	return merge(mergeSort(left), mergeSort(right))
}

const merge = (left, right) => {
	const result = []

	while (left.length && right.length) {
		// 注意：判断的条件是小于或等于，如果只是小于，俺么排序将不稳定
		if (left[0] <= right[0]) {
			result.push(left.shift())
		} else {
			result.push(right.shift())
		}
	}

	while(left.length) result.push(left.shift())
	while(right.length) result.push(right.shift())
	return result
}

module.exports = { mergeSort, merge }


const merge = (a, lo, mid, hi) => {
	let i = lo, j = mid + 1

	for (let k = lo; k <= hi; k++) {
		aux[k] = a[k]
	}

	for (let k = lo; k <= hi; k++) {
		if (i > mid) a[k] = aux[j++]
		else if (j > hi) a[k] = aux[i++]
		else if (a[i] > a[j]) a[k] = aux[j++]
		else a[k] = aux[i++]
	}

}

class Merge {
	aux = []

	static sort(a) {
		this.sort(a, 0, a.length - 1)
	}

	static sort(a, lo, hi) {
		if (hi <= lo) return
		mid = lo + (hi - lo)/2
		sort(a, lo, mid)
		sort(a, mid + 1, hi)
		merge(a, lo, mid, hi)
	}
}